
/*
记忆化搜索
连接:https://leetcode.cn/problems/longest-increasing-subsequence/
题目: 最长递增子序列

   
*/

///记忆化搜索
class Solution {
public:
    int ret;
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n);
        for(int i=0;i<n;i++)
        {
            ret = max(ret,dfs(i,nums,memo));
        }
        return ret;
    }
    int dfs(int i,vector<int>& nums,vector<int>& memo)
    {
        
        if(memo[i] !=0)
            return memo[i];
        int sum = 1;
        for(int j = i+1;j<nums.size();j++)
        {
            if(nums[j]>nums[i])
                sum = max(sum,dfs(j,nums,memo)+1);
        }
        memo[i] = sum;
        return sum;
    }
};
//动规
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        int ret=0;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i+1;j<n;j++)
            {
                if(nums[j]>nums[i])
                    dp[i] = max(dp[i],dp[j]+1);
            }
            ret = max(dp[i],ret);
        }
        // vector<int> memo(n);
        // for(int i=0;i<n;i++)
        // {
        //     ret = max(ret,dfs(i,nums,memo));
        // }
         return ret;
    }